package stu.edu.Sort;

/**
 * 计数排序
 * 稳定排序，时间复杂度为O(n)
 */
public class CountNumSort {

    public static void sort(int[] nums) {
        int numsCount = nums.length;

        int[] cnt = new int[numsCount];
        for (int num : nums) {
            cnt[num] ++;
        }

        int[] index = new int[numsCount+1];
        for (int i = 0; i < numsCount; i++) {
            index[i+1] = index[i] + cnt[i];
        }

        for (int i = 0; i < index.length; i++) {
            // [index[i], index[i+1]) 的值为i
            for (int j = index[i]; j < index[i+1]; j++) {
                nums[j] = i;
            }
        }

    }


}
